{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "\n",
    "class Solution:\n",
    "    def scoreOfParentheses(self, S: str) -> int:\n",
    "        S = re.sub(r\"\\(\\)\", r\"+1\",S)\n",
    "        while 1:\n",
    "            if \"(\" not in S:\n",
    "                break\n",
    "            S = re.sub(r\"\\((?P<expression>[^()]+?)\\)\", r\"+[\\g<expression>]*2\",S)\n",
    "        expression = S.replace(\"[\", \"(\").replace(\"]\", \")\")\n",
    "        #print(expression)\n",
    "        return eval(expression)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Start from 8:40 AM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isAllNumbers(s):\n",
    "    return s.isdecimal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[('', '3', 'a2[c]', '')]\n",
      "[('a', '2', 'c', '')]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"3[a2[c]]\"\n",
    "s = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", s, flags=re.DOTALL)\n",
    "print(s)\n",
    "s = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", s[0][2], flags=re.DOTALL)\n",
    "print(s)\n",
    "s = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", s[0][2], flags=re.DOTALL)\n",
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('', '3', 'a2[c]', '')\n",
      "('a', '2', 'c', '')\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'accaccacc'"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"3[a2[c]]\"\n",
    "temp = \"\"\n",
    "def encode(target):\n",
    "    if \"[\" not in target:\n",
    "        return target\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", target, flags=re.DOTALL)[0]\n",
    "    print(groups)\n",
    "    first = groups[0]\n",
    "    last = groups[3]\n",
    "    if groups[1] != \"\":\n",
    "        times = int(groups[1])\n",
    "    else:\n",
    "        times = 1\n",
    "    subString = groups[2]\n",
    "    return first + times*encode(subString) + last\n",
    "encode(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['3[a]', '2[bc]']"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"3[a]2[bc]\"\n",
    "\n",
    "def countInstances(s):\n",
    "    instances = []\n",
    "    left = 0\n",
    "    right = 0\n",
    "    startPoint = 0\n",
    "    nextStart = True\n",
    "    for i, c in enumerate(s):\n",
    "        if c == \"[\":\n",
    "            left += 1\n",
    "            nextStart = True\n",
    "        elif c == \"]\":\n",
    "            right += 1\n",
    "        if nextStart:\n",
    "            if left!=0 and left == right:\n",
    "                instances.append(s[startPoint:i+1])\n",
    "                startPoint = i + 1\n",
    "                nextStart = False\n",
    "    if len(instances) == 0:\n",
    "        instances = [s]\n",
    "    return instances\n",
    "\n",
    "countInstances(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('', '3', 'a', '')\n",
      "['a']\n",
      "('', '2', 'bc', '')\n",
      "['bc']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'aaabcbc'"
      ]
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"3[a]2[bc]\"\n",
    "\n",
    "def encode(target):\n",
    "    if \"[\" not in target:\n",
    "        return target\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", target, flags=re.DOTALL)[0]\n",
    "    print(groups)\n",
    "    first = groups[0]\n",
    "    last = groups[3]\n",
    "    if groups[1] != \"\":\n",
    "        times = int(groups[1])\n",
    "    else:\n",
    "        times = 1\n",
    "    subString = groups[2]\n",
    "    instances = countInstances(subString)\n",
    "    print(instances)\n",
    "    return first + times*\"\".join([encode(instance) for instance in instances]) + last\n",
    "\n",
    "\"\".join([encode(instance) for instance in countInstances(s)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the groups:  ('', '2', 'abc]3[cd', 'ef')\n",
      "encode groups:  ('', '2', 'abc', '')\n",
      "['abc']\n",
      "encode groups:  ('', '3', 'cd', '')\n",
      "['cd']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'abcabccdcdcdef'"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def countInstances(s):\n",
    "    instances = []\n",
    "    left = 0\n",
    "    right = 0\n",
    "    startPoint = 0\n",
    "    nextStart = True\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", s, flags=re.DOTALL)\n",
    "    for i, c in enumerate(s):\n",
    "        if c == \"[\":\n",
    "            left += 1\n",
    "            nextStart = True\n",
    "        elif c == \"]\":\n",
    "            right += 1\n",
    "        if nextStart:\n",
    "            if left!=0 and left == right:\n",
    "                instances.append(s[startPoint:i+1])\n",
    "                startPoint = i + 1\n",
    "                nextStart = False\n",
    "    if len(instances) == 0:\n",
    "        instances = [s]\n",
    "    if len(groups) > 0:\n",
    "        groups = groups[0]\n",
    "        print(\"the groups: \", groups)\n",
    "        first = groups[0]\n",
    "        last = groups[3]\n",
    "        return [first] + instances + [last]\n",
    "    else:\n",
    "        return instances\n",
    "\n",
    "\n",
    "def encode(target):\n",
    "    if \"[\" not in target:\n",
    "        return target\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", target, flags=re.DOTALL)[0]\n",
    "    print(\"encode groups: \", groups)\n",
    "    first = groups[0]\n",
    "    last = groups[3]\n",
    "    if groups[1] != \"\":\n",
    "        times = int(groups[1])\n",
    "    else:\n",
    "        times = 1\n",
    "    subString = groups[2]\n",
    "    instances = countInstances(subString)\n",
    "    print(instances)\n",
    "    return first + times*\"\".join([encode(instance) for instance in instances]) + last\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        return \"\".join([encode(instance) for instance in countInstances(s)])\n",
    "\n",
    "\"abcabccdcdcdef\"\n",
    "Solution().decodeString(\"2[abc]3[cd]ef\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the groups:  ('', '3', 'a2[c]', '')\n",
      "encode groups:  ('', '3', 'a2[c]', '')\n",
      "the groups:  ('a', '2', 'c', '')\n",
      "['a2[c]', '']\n",
      "encode groups:  ('a', '2', 'c', '')\n",
      "['c']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'accaccacc'"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def countInstances(s):\n",
    "    instances = []\n",
    "    left = 0\n",
    "    right = 0\n",
    "    startPoint = 0\n",
    "    nextStart = True\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", s, flags=re.DOTALL)\n",
    "    for i, c in enumerate(s):\n",
    "        if c == \"[\":\n",
    "            left += 1\n",
    "            nextStart = True\n",
    "        elif c == \"]\":\n",
    "            right += 1\n",
    "        if nextStart:\n",
    "            if left!=0 and left == right:\n",
    "                instances.append(s[startPoint:i+1])\n",
    "                startPoint = i + 1\n",
    "                nextStart = False\n",
    "    if len(instances) == 0:\n",
    "        instances = [s]\n",
    "    if len(groups) > 0:\n",
    "        groups = groups[0]\n",
    "        print(\"the groups: \", groups)\n",
    "        first = groups[0]\n",
    "        last = groups[3]\n",
    "        return instances + [last]\n",
    "    else:\n",
    "        return instances\n",
    "\n",
    "\n",
    "def encode(target):\n",
    "    if \"[\" not in target:\n",
    "        return target\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", target, flags=re.DOTALL)[0]\n",
    "    print(\"encode groups: \", groups)\n",
    "    first = groups[0]\n",
    "    last = groups[3]\n",
    "    if groups[1] != \"\":\n",
    "        times = int(groups[1])\n",
    "    else:\n",
    "        times = 1\n",
    "    subString = groups[2]\n",
    "    instances = countInstances(subString)\n",
    "    print(instances)\n",
    "    return first + times*\"\".join([encode(instance) for instance in instances]) + last\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        return \"\".join([encode(instance) for instance in countInstances(s)])\n",
    "\n",
    "\"accaccacc\"\n",
    "Solution().decodeString(\"3[a2[c]]\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/decode-string\n",
    "\n",
    "\n",
    "\n",
    "Runtime: 32 ms, faster than 37.42% of Python3 online submissions for Decode String.\n",
    "Memory Usage: 14.3 MB, less than 6.07% of Python3 online submissions for Decode String.\n",
    "\n",
    "\n",
    "\n",
    "```python\n",
    "def countInstances(s):\n",
    "    instances = []\n",
    "    left = 0\n",
    "    right = 0\n",
    "    startPoint = 0\n",
    "    nextStart = True\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", s, flags=re.DOTALL)\n",
    "    for i, c in enumerate(s):\n",
    "        if c == \"[\":\n",
    "            left += 1\n",
    "            nextStart = True\n",
    "        elif c == \"]\":\n",
    "            right += 1\n",
    "        if nextStart:\n",
    "            if left!=0 and left == right:\n",
    "                instances.append(s[startPoint:i+1])\n",
    "                startPoint = i + 1\n",
    "                nextStart = False\n",
    "    if len(instances) == 0:\n",
    "        instances = [s]\n",
    "    if len(groups) > 0:\n",
    "        groups = groups[0]\n",
    "        print(\"the groups: \", groups)\n",
    "        first = groups[0]\n",
    "        last = groups[3]\n",
    "        return instances + [last]\n",
    "    else:\n",
    "        return instances\n",
    "\n",
    "\n",
    "def encode(target):\n",
    "    if \"[\" not in target:\n",
    "        return target\n",
    "    groups = re.findall(r\"([A-Za-z]*)(\\d*)\\[(.*)\\]([A-Za-z]*)\", target, flags=re.DOTALL)[0]\n",
    "    print(\"encode groups: \", groups)\n",
    "    first = groups[0]\n",
    "    last = groups[3]\n",
    "    if groups[1] != \"\":\n",
    "        times = int(groups[1])\n",
    "    else:\n",
    "        times = 1\n",
    "    subString = groups[2]\n",
    "    instances = countInstances(subString)\n",
    "    print(instances)\n",
    "    return first + times*\"\".join([encode(instance) for instance in instances]) + last\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        return \"\".join([encode(instance) for instance in countInstances(s)])\n",
    "\n",
    "\"accaccacc\"\n",
    "Solution().decodeString(\"3[a2[c]]\")\n",
    "```\n",
    "\n",
    "\n",
    "Spent 5 hours\n",
    "\n",
    "Two shoot but with many experiments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}